import com.sun.org.apache.bcel.internal.generic.IF_ACMPEQ;

import java.util.*;

/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-02-21
 * Time:10:24
 */

/**
 * 838. 推多米诺
 * n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。
 * 每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。
 * 如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。
 * 就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。
 * 给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：
 * dominoes[i] = 'L'，表示第 i 张多米诺骨牌被推向左侧，
 * dominoes[i] = 'R'，表示第 i 张多米诺骨牌被推向右侧，
 * dominoes[i] = '.'，表示没有推动第 i 张多米诺骨牌。
 * <p>
 * 思路1
 * 解题思路 分情况来模拟
 * '..L' : 左侧都填充L
 * 'L..L' : 两个L之间要填充L
 * 'R..L' : R,L之间要双指针夹逼
 * 'R..R' : 两个R之间填充R
 * 'R..' : 右侧都填充R
 */
public class TestDemo {
    public static String pushDominoes(String dominoes) {
        char[] s = dominoes.toCharArray();
        int n = dominoes.length();
        //记录答案
        char[] ans = dominoes.toCharArray();
        //记录 'R''L'的位置
        Queue<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            if (s[i] == 'L' || s[i] == 'R') {
                deque.offer(i);
            }
        }
        while (!deque.isEmpty()) {
            int[] dis = new int[deque.size()];
            int length = deque.size();
            //把'R' 'L'的位置全放在数组里
            for (int i = 0; i < length; i++) {
                dis[i] = deque.poll();
            }
            for (int i = 0; i < dis.length; i++) {
                int flag = dis[i];
                //如果是'L'并且下标在合理的范围内进入
                if (s[flag] == 'L' && flag - 1 >= 0) {
                    //如果'L'位于第一个位置   s[flag - 1] != 'R'是为了防止 RL的情况进入
                    if (flag - 1 == 0 && s[flag - 1] != 'R') {
                        ans[flag - 1] = 'L';
                        //把更新为'L'的下标记录
                        deque.add(flag - 1);
                    } else if (flag - 1 > 0 && s[flag - 2] != 'R' && s[flag - 1] != 'R') {
                        //如果在中间,l前面两个都不是r的时候,把.更新为l
                        ans[flag - 1] = 'L';
                        deque.add(flag - 1);
                    } else {//其他情况不做修改

                    }
                }
                if (s[flag] == 'R' && flag + 1 < n) {
                    //如果'R'位于最后一个位置  s[flag+ 1]  != 'L'是为了防止 RL的情况进入
                    if (flag + 1 == n - 1 && s[flag + 1] != 'L') {
                        ans[flag + 1] = 'R';
                        deque.add(flag + 1);
                    } else if (flag + 1 < n - 1 && s[flag + 2] != 'L' && s[flag + 1] != 'L') {
                        //如果在中间,r后面两个都不是l的时候,把.更新为r
                        ans[flag + 1] = 'R';
                        deque.add(flag + 1);
                    } else {

                    }
                }
            }
            //更新一轮s,代表上一轮的r和l以及跌过,进行下一轮的r和l的跌倒
            s = Arrays.copyOf(ans, n);
        }
        return String.valueOf(ans);
    }

    public static void main(String[] args) {
        String dominoes = "RR......L";
        System.out.println(pushDominoes(dominoes));
        //...RL....R.L.L........RR......L....R.L.....R.L..RL....R....R......R.......................LR.R..L.R.
        //...RL....R.LLL........RRRRR.LLL....R.L.....R.L..RL....RRRRRRRRRRRRRRRRRRRRRRRR.LLLLLLLLLLLLRRRRLL.RR
        //...RL....R.LLL........RRRRRLLLL....R.L.....R.L..RL....RRRRRRRRRRRRRRRRRRRRRRRR.LLLLLLLLLLLLRRRRLL.RR
    }

    //双指针

    /**
     * 今天这道题，可以使用双指针来求解。
     * <p>
     * 我们可以找到每一段连续的 . ，然后判断其两边的字符分别是什么，再对应着来处理：
     * <p>
     * 如果两边都是 R，则把 . 全部替换成 R；
     * 如果左边是 R，右边是边界，则把 . 全部替换成 R；
     * 如果两边都是 L，则把 . 全部替换成 L；
     * 如果左边是边界，右边是 L，则把 . 全部替换成 L；
     * 如果左边是 R，右边是 L，则需要一一对应着来替换，且正好中间那个 . 不需要替换。
     */
    public static String pushDominoes1(String dominoes) {
        //先找到一段连续的...双指针处理进行替换
        char[] arr = dominoes.toCharArray();
        int i = 0;
        while (i < arr.length) {
            //跳过非 . 的字符
            while (i < arr.length && arr[i] != '.') {
                i++;
            }
            //读取连续的.
            int j = i;
            while (j < arr.length && arr[j] == '.') {
                j++;
            }
            //进行替换
            replace(arr, i, j - 1);
            //下一非 . 从j开始进入循环
            i = j;
        }
        return new String(arr);
    }

    private static void replace(char[] arr, int start, int end) {
        // 如果两头都是R，全部替换成R
        // 如果左边是R，右边是边界，全部替换成R
        // 如果两头都是L，全部替换成L
        // 如果左边是边界，右边是L，全部替换成L
        // 如果左边是R，右边是L，除了最中间那个.，其他的都需要替换
        // 其他情况保持不变

        // 如果左边是R，右边是边界，全部替换成R // 如果两头都是R，全部替换成R
        if (start - 1 >= 0 && arr[start - 1] == 'R' && (end + 1 > arr.length || arr[end + 1] == 'R')) {
            while (start <= end) {
                arr[start++] = 'R';
                arr[end--] = 'R';
            }
        } else if (end + 1 < arr.length && arr[end + 1] == 'L' && (start - 1 < 0 || arr[start - 1] == 'L')) {
           // 如果左边是边界，右边是L，全部替换成L   // 如果两头都是L，全部替换成L
            while (start <= end) {
                arr[start++] = 'L';
                arr[end--] = 'L';
            }
        } else if (start - 1 >= 0 && end + 1 < arr.length && arr[start - 1] == 'R' && arr[end + 1] == 'L') {
            //如果左边是R，右边是L，除了最中间那个.，其他的都需要替换
            while (start < end) {
                arr[start++]='R';
                arr[end--]='L';
            }
        }
    }
}
